package com.atwy.graph.directedgraph;

import java.util.Stack;

/**
 * @Author: 小王子火
 * @Date: 2022/3/18
 * 有向环的检测：系统维护的递归调用的栈表示正是“当前”正在遍历的有向路径。
 * 一旦找到一条有向边v->w且w已存在于栈中，说明找到了一个环，因为栈表示的是一条由w到v的有向路径，
 * 而v->w正好补全了这个环。
 */
public class DirectedCycle {
    /**
     * 记录某个顶点是否被访问到
     */
    private boolean[] marked;

    /**
     * v->w 则edgeTo[w] = v
     */
    private int[] edgeTo;

    /**
     * 有向环中所有顶点
     */
    private Stack<Integer> cycle;
    /**
     * 递归调用的栈上的所有顶点
     */
    private boolean[] onStack;

    public DirectedCycle(IDigraph graph) {
        marked = new boolean[graph.V()];
        onStack = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        for (int s = 0; s < graph.V(); s++) {
            if (!marked[s]) {
                dfs(graph, s);
            }
        }

    }

    private void dfs(IDigraph graph, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : graph.adj(v)) {
            if (this.hasCycle()) {
                return;
            } else if (!marked[w]) {
                // 没有被访问到，那就记录路径，继续递归
                edgeTo[w] = v;
                dfs(graph, w);
            } else if (onStack[w]) {
                // w被访问到了，而且在栈上，说明存在了环
                cycle = new Stack<>();
                // 记录有向环的轨迹,源头是v,也就是说明此时存在w->v,而在本次递归中w是v的邻接点，也就是v->w
                // 那就沿v倒推回w这样就把环上所有点都找到了
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                // 再把w放进轨迹栈中
                cycle.push(w);
                // 为了表明轨迹是一个环，还应把v压进栈中,上面for循环第一压进去的就是v
                cycle.push(v);
            }
        }
        // v深度访问之后没有环，则将v踢出栈记录
        onStack[v] = false;
    }

    /**
     * 返回是否存在环
     *
     * @return
     */
    public boolean hasCycle() {
        return cycle != null;
    }
}
